package leetcode;

import util.Tree;
import util.TreeNode;

/**
 * @Project : AlgorithmLearning
 * @Package : Leetcode
 * @File : Q0654.java
 * @Author : WangRuoyu
 * @Date 2023/10/23 19:59
 */


public class Q0654 {
    int[] nums;

    private TreeNode createMaximumBinaryTree(int l, int r) {
        if (l <= r) {
            int k = 0;
            int max = -1;
            for (int i = l; i <= r; i++) {
                if (nums[i] > max) {
                    k = i;
                    max = nums[i];
                }
            }
            TreeNode node = new TreeNode(max);
            node.left = createMaximumBinaryTree(l, k - 1);
            node.right = createMaximumBinaryTree(k + 1, r);
            return node;
        }
        return null;
    }

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        this.nums = nums;
        return createMaximumBinaryTree(0, nums.length - 1);
    }

    public static void main(String[] args) {
        Q0654 sl = new Q0654();
        int[] nums = {3, 2, 1, 6, 0, 5};
        Tree.preorderTraversal(sl.constructMaximumBinaryTree(nums));
    }
}